おきらくＰｅｒｌプログラミング入門
～～めざせ Perl マスター～～
広井 誠
第１６回
○オブジェクト指向編（その２）
前回は、一般的なオブジェクト指向の話とパッケージの使い方を説明しました。
今回は、簡単なプログラムを作りながら、具体的に Perl のオブジェクト指向を
説明していきます。
○クラスの定義とインスタンスの生成
Perl では、クラスの定義はパッケージで行います。簡単な例として、点を表
す Point クラスを作ってみましょう。
List 1 : Point クラス
1 package Point;
2
3 # インスタンスを生成するメソッド
4 sub new {
5 my ($x,$y) = @_;
6 my $obj = { 'x' => $x, 'y' => $y };
7 bless $obj, 'Point';
8 $obj;
9 }
一般に、クラス名は英大文字から始めることが多いので、パッケージ名は
Point としました。関数 new はインスタンスを生成するメソッドです。new は
インスタンスを操作するのではなく、クラスの動作にかかわるメソッドです。こ
のようなメソッドを「クラスメソッド」といい、インスタンスを操作するメソッ
ドを「インスタンスメソッド」といいます。
メソッド new は引数として座標 x, y を受け取り、インスタンスを生成しま
す。前回説明したように、Perl では配列でもハッシュでもスカラー変数でも、
リファレンスで指し示すことができるものであれば何でも、インスタンスとして
扱うことができますが、添字でデータの種類を表すことができるハッシュを使う
ことが多いようです。そこでインスタンスはハッシュで表し、x 座標は添字 'x'
に、y 座標は添字 'y' に格納することにします。この 2 つのデータで点の座標
を表します。
生成したハッシュをインスタンスとして扱うには、 関数 bless を使ってクラ
スの印をつけます。
bless リファレンス, クラス名
bless は、リファレンスが指し示すデータに、クラスに属するインスタンスであ
ることを示す印を付けます。Perl では、この操作を「ブレス[*1] する」といい
ます。第 1 引数にリファレンスを与え、第 2 引数にクラス名（パッケージ名）
を指定します。第 2 引数を省略するとカレントパッケージが指定されます。た
だし、クラス名を省略するとメソッドの継承が動作しないことがあるので、面倒
だとは思わずにクラス名を書くようにしてください。最後に、メソッド new の
返り値として生成したオブジェクト返します。
メソッド new の呼び出しは、次のように行います。
$p1 = Point::new( 0, 0 );
Perl の場合、メソッドは関数にすぎません。通常の関数と同じく、Point クラ
スで定義されているメソッド new を呼び出すことができます。ところが、クラ
ス名を明示すると、ポリモーフィズムを利用することができません。このため、
メソッドの呼び出しには特別な構文が用意されていて、そちらを使用するのが普
通です。これは次のインスタンスメソッドで説明します。
note:
[*1] ブレス(bless) は、清める、祝福する、という意味ですが、この連載では
Perl 本[1]の日本語訳に従うことにします。
○メソッドの呼び出し
それでは、インスタンスを操作するメソッドとして、2 点間の距離を計算する
distance を作ってみます。当然ですが、distance はパッケージ Point 内で定
義します。
List 2 : 2 点間の距離を計算する
1 sub distance {
2 my ($obj1, $obj2) = @_;
3 my $dx = $obj1->{'x'} - $obj2->{'x'};
4 my $dy = $obj1->{'y'} - $obj2->{'y'};
5 sqrt( $dx * $dx + $dy * $dy );
6 }
メソッド distance は Point クラスのインスタンスを 2 つ受け取り、その距離
を計算します。distance の定義自体は、インスタンス（ハッシュ）から座標を
取り出して距離を計算するだけです。
メソッド distance は、次のように呼び出すことができます。
$p1 = Point::new( 0, 0 );
$p2 = Point::new( 10, 10 );
$len = $p1->distance( $p2 );
矢印「->」はメソッドを呼び出す構文です。最初に Perl は $p1 が属するクラ
スを調べます。$p1 には Point クラスのインスタンスが格納されていますね。
そこで Perl は Point クラスに定義されているメソッドを調べ、該当するメソッ
ド distance を呼び出すのです。これは、次のような関数形式の呼び出しと同じ
です。
Point::distacne( $p1, $p2 );
矢印左側のインスタンスを第 1 引数として、そのクラスのメソッドが呼び出
されます。ここで、矢印を使ったメソッドの呼び出しは、クラス名を明示する通
常の関数呼び出しと違い、矢印左側のインスタンスによって適切なメソッドが選
択されることに注意してください。たとえば、3 次元の座標を表す Point3D ク
ラスを考えてみましょう。
List 3 : 3 次元の座標を表す
1 package 'Point3D';
2
3 # インスタンスの生成
4 sub new {
5 my ($x,$y,$z) = @_;
6 my $obj = { 'x' => $x, 'y' => $y, 'z' => $z };
7 bless $obj, 'Point3D';
8 $obj;
9 }
10
11 # 2 点間の距離を求める
12 sub distance {
13 my ($obj1, $obj2) = @_;
14 my $dx = $obj1->{'x'} - $obj2->{'x'};
15 my $dy = $obj1->{'y'} - $obj2->{'y'};
16 my $dz = $obj1->{'z'} - $obj2->{'z'};
17 sqrt( $dx * $dx + $dy * $dy + $dz * $dz );
18 }
クラス Point3D は、Point を 3 次元に拡張しただけです。Point でも Point3D
でも距離を計算するメソッド distance が定義されていることに注目してくださ
い。それでは、メソッド distance を呼び出してみましょう。
$p1 = Point::new( 0, 0 );
$p2 = Point::new( 10, 10 );
$p3 = Point3D::new( 0, 0, 0 );
$p4 = Point3D::new( 10, 10, 10 );
$len1 = $p1->distance( $p2 ); # Point クラスの distance
$len2 = $p3->distance( $p4 ); # Point3D クラスの distance
このように、矢印左側のインスタンスによって、適切なメソッドが呼び出される
ことがわかります。これを「ポリモーフィズム(polymorphism)」といいます。も
しも、ポリモーフィズムを利用せずにプログラムすると、distance の中でイン
スタンスの種類をチェックしなければいけません。インスタンスの種別を調べる
には関数 ref を使います。
ref リファレンス
関数 ref は与えられた引数がリファレンスならば、リファレンスが示すデータ
の種別を文字列として返します。引数がリファレンスでなければ、空文字列を返
します。
REF リファレンス
SCALAR スカラー
ARRAY 配列
HASH ハッシュ
CODE コード
GLOB グラブ
もしもリファレンスが指しているデータがブレスされていたならば、そのクラス
名を返します。ref を使って distance を書き換えると、次のようになります。
List 4 : ポリモーフィズムを使わない distance
1 sub distance {
2 my ($obj1,$obj2) = @_;
3 my $type = ref( $obj1 );
4 if( $type == 'Point' ){
5 my $dx = $obj1->{'x'} - $obj2->{'x'};
6 my $dy = $obj1->{'y'} - $obj2->{'y'};
7 sqrt( $dx * $dx + $dy * $dy );
8 } elsif( $type == 'Point3D' ){
9 my $dx = $obj1->{'x'} - $obj2->{'x'};
10 my $dy = $obj1->{'y'} - $obj2->{'y'};
11 my $dz = $obj1->{'z'} - $obj2->{'z'};
12 sqrt( $dx * $dx + $dy * $dy + $dz * $dz );
13 } else {
14 die("処理できないデータです\n");
15 }
16 }
distance は 2 つのデータを扱うだけなので、プログラムはそれほど複雑にはな
りません。しかし、たくさんのデータを扱うようになると、それだけプログラム
は複雑になります。特に、新しいデータを追加するような場合、プログラムの内
部でデータの種別をチェックしている箇所を全て調べて、そこに新しい処理を追
加しなければいけません。プログラムの規模が大きくなると、修正箇所を調べる
だけでも大変です。ところが、ポリモーフィズムを使ってプログラムすると、新
しいデータを追加するにしても、そのデータを表すクラスとメソッドを定義する
だけでいいのです。後は Perl がインスタンスに合わせて適切なメソッドを呼び
出してくれます。オブジェクト指向では、オブジェクトを一つの部品として扱い
ます。新しい部品を追加するにしても、今までの部品を修正せずにそのまま使え
た方が便利ですね。
ところで、クラスメソッド new も矢印形式で呼び出すことができます。
$p1 = Point->new( 0, 0 );
矢印の左側がクラス名の場合、そのクラスに定義されている関数が呼び出されま
す。この場合、クラス名 Point が第 1 引数として渡されることに注意してくだ
さい。そこで、矢印形式で new を呼び出せるように改造してみましょう。
List 5 : インスタンスの生成（改造版）
1 sub new {
2 my ($type, $x, $y) = @_;
3 my $dx = $obj1->{'x'} - $obj2->{'x'};
4 my $dy = $obj1->{'y'} - $obj2->{'y'};
5 sqrt( $dx * $dx + $dy * $dy );
6 }
このようにクラスメソッドを定義すると、適切なクラスのインスタンスを簡単に
生成することができます。たとえば、変数 $tmp にクラス名が格納されている場
合、第 1 引数にパッケージ名を受け取るように new を定義すると、次のように
呼び出すことができます。
$tmp->new();
これだけで $tmp に格納されたクラスのインスタンスを生成することができます。
それから第 1 引数 $type をチェックすることで、インスタンスメソッドとし
ての機能を持たせることもできます。たとえば、インスタンスのコピー[*2]を生
成する場合にも new というメソッドを使うことにしましょう。この場合、関数
ref で第 1 引数をチェックして、返り値が空文字列であれば、引数はパッケー
ジ名なので新しいインスタンスを生成し、そうでなければ引数はインスタンスな
ので、そのコピーを生成するように new を定義することができます。この他に、
第 1 引数にパッケージ名を受け取らないクラスメソッドだと、そのクラスを継
承した時に困ることがあるのです。詳しい内容は継承の時に説明しますが、メソッ
ドは第 1 引数にクラス名かオブジェクトを受け取るように作ることにします。
note:
[*2] オブジェクト指向では「クローン(clone)」と呼ぶことがあります。
○二分探索木
簡単な例題として、「二分探索木」という探索アルゴリズムを Perl で実装し
てみましょう。あるデータの中から特定のデータを探す場合、データ数が少なけ
れば力任せに検索しても何とかなりますが、データ数が多くなると検索に時間が
かかるようになります。このような場合、あらかじめデータを整理整頓しておく
ことで、特定のデータを高速に見つけることができるようになります。この代表
的なアルゴリズムが「ハッシュ法」と「二分探索木」です。Perl の連想配列は
ハッシュ法を使って実装されているので、ハッシュと呼ばれています。
第 14 回で８パズルの解法を取り上げましたが、このプログラムでは同一局面
のチェックが必要になります。実は、配列を使った単純な線形探索を使うと、メ
チャクチャ時間がかかるのです。このため、Perl 版ではハッシュを、Ｃ言語版
では二分探索木を用いました。Perl にはハッシュが用意されているので、二分
探索木を使う機会は少ないでしょう。ですが、二分探索木にはハッシュにはない
特徴があります。格納されたデータをある順番で出力すると、それはソートした
結果と同じになるのです。また、データの中から最大値や最小値を簡単に見つけ
ることもできます。データを見つけることだけならばハッシュの方が高速なので
すが、データの大小関係が絡む処理には、二分探索木の方が適しています。
二分探索木はその名が示すように「木構造」の一種です。まずは木構造から説
明しましょう。
○木構造
「木構造(tree structer)」は「木(tree)」とも呼ばれるデータ構造で、節
（ノード）と呼ばれる要素に対して、階層的な関係を表したものです。身近な例
では、ディレクトリの階層構造が木にあたります。ディレクトリに「ルートディ
レクトリ」があるように、木にも「根（ルート）」と呼ばれる節が存在します。
(root)
Ａ ──────── レベル０
／｜＼ ↑
／ ｜ ＼
Ｂ Ｃ Ｄ 木 レベル１
／｜＼ ｜＼ の
／ ｜ ＼ ｜ ＼ 高
Ｅ Ｆ Ｇ Ｈ Ｉ さ レベル２
／ ＼
／ ＼ ↓
Ｊ Ｋ ───── レベル３
図 1 : 一般的な木構造の一例
木を図示する場合、階層関係がはっきりわかるように、根を上にして、同じ階
層にある節を並べて書きます。
根からレベル 0、レベル 1 と階層を数えていき、最下層の節までの階層数を
「木の高さ」といいます。木は、ある節から下の部分を切り出したものも、木と
しての性質を持っています。これを「部分木」といいます。
木は、ある節から他の節に至る「経路」を考えることができます。たとえば、
ＡからＪには、Ａ－Ｂ－Ｇ－Ｊという経路がありますね。これは、ディレクトリ
やファイルを指定する時のパスと同じです。
ある節から根の方向にさかのぼる時、途中で通っていく節を「先祖」といい、
直接繋がっている節を「親」といます。これは、逆から見ると「子孫」と「子」
という関係になります。子を持たない節を特に「葉」と呼ぶことがあります。上
図でいうと、ＧはＪ，Ｋの親で、ＪはＧの子になります。Ｊは子を持っていない
ので葉となります。
子は、「左 < 右」の順番で節に格納するのが一般的です。これを「順序木」
といいます。また、順番が無い木を「無順序木」と呼びます。
節が持っている子の数を「次数」といいます。上図の場合、Ａは 3 つの子Ｂ、
Ｃ、Ｄを持っているので、Ａの次数は 3 となります。全ての節の次数を n に揃
えた順序木を「n 分木」と呼びます。特に、次数が 2 の二分木は、プログラム
でよく使われるデータ構造です。
(root)
18
／ ＼
／ ＼
／ ＼
／ ＼
／ ＼
14 22
／ ＼ ／ ＼
／ ＼ ／ ＼
12 16 20 24
／ ＼ ／ ＼ ／ ＼ ／ ＼
11 13 15 17 19 21 23 25
図 2 : 二分木の一例
上図に二分木の例を示します。二分木では、節に一つのデータを格納します。
そして、その節の左側の子には小さいデータを、右側の子には大きいデータが配
置されるように木を構成します。
この二分木をデータの探索に使うアルゴリズムが「二分探索木」です。二分探
索木はデータの探索・挿入を高速に行うことができます。たとえば、上図の木か
ら 19 を探してみましょう。まず root の 18 と比較します。18 < 19 ですから、
右側の子をたどり 22 と比較します。今度は 19 < 22 なので左側の子をたどり
ます。次は 20 と比較し 19 < 20 なので左側の子をたどり、ここで 19 を見つ
けることができます。
二分探索木の探索は二分探索と同じ原理です。左右どちらかの子をたどるたび
に、探索するデータ数は半分になります。上図の場合でも、探索するデータ数が
15, 7, 3, 1 となり、最後に見つけることができました。
データ数を N とすると、単純な線形探索では平均で N/2 回の比較が必要にな
りますが、二分探索木を使うと log N 程度の回数で収まります。たとえば、デー
タが 100個ある場合、線形探索では 50 回データを比較しなければいけないのに、
二分探索木では 7 回程度の比較で済むわけです。
ただし、これは左右の部分木のバランスがとれている理想的な状態での話です。
バランスが崩れると二分探索木の性能は劣化し、最悪の場合は線形探索と同じに
なってしまいます。そこで、左右のバランスを一定の範囲に収める「平衡木」が
考案されています。有名なところでは AVL 木、2-3 木、B 木、B* 木などがあり
ます。また、Ｃ++の標準ライブラリである STL(Standard Template Library) で
は、「赤黒木」というアルゴリズムが使われているそうです。AVL 木については
拙作の「Ｚしーモンキーほしゅうの時間その１０(月刊・電脳倶楽部 Vol.95)」
で説明しているので、興味のある方は参考にしてください。
○データの探索
それでは実際に二分探索木を作っていきましょう。二分探索木の場合、データ
の大小関係をチェックする処理が必要になります。たとえば、格納するデータが
数値であれば演算子 <=> を、文字列であれば演算子 cmp を使ってチェックする
ことができます。ところが、データを比較する処理をそのままプログラムすると、
そのデータしか使うことができない二分探索木になってしまいます。つまり、演
算子 <=> を使えば数値だけしか使えず、演算子 cmp を使えば文字列だけにしか
使うことができません。したがって、新しいデータに対応するためには、データ
を比較する処理を書き換えなければならないのです。これでは面倒ですね。そこ
で、あらゆるデータに対応できるようプログラムしてみましょう。これは、オブ
ジェクト指向を使えば簡単に実現できます。もうおわかりの方もいるでしょうが、
二分探索木に格納するデータはクラスで表し、データの比較はそのクラスで定義
されたメソッドを呼び出せばいいのです。ポリモーフィズムにより適切なメソッ
ドが選択されるため、二分探索木のプログラムは修正する必要がなくなるのです。
まずデータ構造を決定しましょう。節はハッシュを使って表すことにします。
このハッシュもオブジェクトとして扱います。クラス名は Bintree としました。
格納するデータは item に、左の子は left に、右の子は right に格納するこ
とにします。left の子を取り出せば、左側の部分木へ移動することができ、right
の子を取り出せば、右側の部分木へ移動することができます。子が無い場合には、
木の終端を表すためのオブジェクトを格納します。このオブジェクトは空のハッ
シュで表し、あらかじめ大域変数 $nil に格納しておきます。当然ですが、空の
ハッシュもブレスしておきます。この処理はパッケージの先頭で行っておきます。
List 6 : 二分探索木
1 package Bintree;
2
3 # 終端を示す nil 用無名空ハッシュ
4 $nil = {};
5 bless $nil, 'Bintree';
6
7 # 二分探索木の初期化
8 sub make_tree { $nil; }
クラスメソッド make_tree は、二分探索木の初期化を行います。これは $nil
に格納されているインスタンスを返すだけですが、これにより空の二分探索木を
設定することができます。二分探索木を使う場合は、最初に make_tree を実行
して二分探索木を初期化します。
$root = Bintree->make_tree();
大域変数 $nil に直接アクセスすることもできますが、メソッドを経由してデー
タを操作するのがオブジェクト指向の基本です。インスタンス内の変数を読み書
きする場合も同じです。データの読み書きを行うメソッドを「アクセスメソッド」
といいます。わざわざアクセスメソッドを用意するのは面倒ですが、アクセスメ
ソッドの仕様さえわかっていれば、クラスの詳細な構造を知る必要はありません。
つまり、アクセスメソッドを定義することで、データ構造を覆い隠すことができ
るのです。これを「データ抽象」とか「カプセル化」といます。
プログラムに修正はつきもので、「あそこを変更したら、ここが動かなくなっ
た」ということはよくあることです。ある時には、クラス内のデータ構造そのも
のを変更しなければならない場合もあります。この場合でもカプセル化を行って
いれば、アクセスメソッドを変更するだけなので、他の関数に影響を与えること
はありません。たとえば、大域変数 $nil の名前を変更してみましょう。メソッ
ド make_tree を使っていれば、make_tree を変更するだけで他のプログラムを
修正する必要はありませんね。ところが、直接 $nil にアクセスしている場合、
まず Bintree を利用しているプログラムを探し、その中から $nil にアクセス
している箇所を全て修正しなければいけません。これはとても面倒で退屈な作業
ですね。カプセル化を行うことで、機能追加や修正に強いプログラムを作ること
ができるのです。
次は、二分探索木からデータを探すメソッドを作ります。search_tree は節と
探索するオブジェクトを引数として受け取り、次のように呼び出します。
$root->insert_tree( $object );
$root が空の二分探索木の場合でも、空のハッシュ($nil)は Bintree にブレス
されているので、insert_tree を呼び出すことができます。search_tree はデー
タが見つかったならば 1 を、見つからなければ 0 を返します。プログラムは次
のようになります。
List 7 : データの探索
1 sub search_tree {
2 my ($node, $item) = @_;
3 while( $node != $nil ){
4 my $result = $item->compare( $node->{'item'} );
5 if( $result == 0 ){
6 return 1;
7 } elsif( $result < 0 ){
8 $node = $node->{'left'};
9 } else {
10 $node = $node->{'right'};
11 }
12 }
13 0;
14 }
3 行目の while ループで、木の終端に達するまでインスタンスの比較を繰り
返します。$node と $nil には節を表すインスタンス（ハッシュ）へのリファレ
ンスが格納されていますが、それを数値演算子 != で比較しています。Perl の
場合、処理に合わせて適当なデータ変換が行われますが、リファレンスの場合、
それが指し示すデータのアドレスを数値に変換して比較します。ここで、インス
タンスの実体であるハッシュは、メモリの中に存在することに注意してください。
これは空のハッシュも例外ではありません。ハッシュは作成されるたびに、別の
メモリが割り当てられます。したがって、アドレスが同じであれば、同一のハッ
シュ（インスタンス）と判断することができます。
ここで、同一というのは同じ値を持つインスタンスとは違う、ということに注
意してください。たとえば、数値を格納するクラスを考えてみましょう。インス
タンス A は 10 を格納しています。次に、新しいインスタンス B を作成し、そ
の値を 10 にセットしました。インスタンス A と B は、異なるメモリに割り当
てられた異なるインスタンスですが、同じ値 10 を持っています。この時、イン
スタンス A と B を同値[*3]といいます。
プログラムの説明に戻りましょう。4 行目で、データの比較を行います。ここ
でデータを比較するメソッド compare を呼び出します。当然ですが、データを
表すクラスを作る時には、メソッド compare の定義を忘れてはいけません。こ
れだけのことで、あらゆるデータに対して二分探索木が動作するようになるので
す。
compare が返す結果は、演算子 <=>, cmp に合わせて -1, 0, 1 とします。結
果は変数 $result に格納します。もし $result が 0 ならば、同じデータを見
つけたので 1 を返します。$result が -1 ならば、$item の方が小さいので左
側の子へ進みます。そうでなければ右側の子へ進みます。木の終端まで達したな
らば、while ループを抜けて 0 を返します。
note:
[*3] Lisp プログラミングの経験がある方ならば、データを比較する関数 eq
と equal を思い出すことでしょう。Lisp の場合、データの同一をチェッ
クするのが eqで、同値をチェックするのが equal です。Lisp では、数
値 10 と 10 を equal で比較すると必ず「真」となりますが、10 と 10
を eq で比較しても真とはならないことがあります。
○データの挿入
次は、二分探索木にデータを挿入するメソッド insert_tree を作りましょう。
このメソッドは次のように呼び出します。
$root = $root->insert_tree( $item );
insert_tree は二分探索木 $node にデータを挿入し、その二分探索木を返しま
す。これは再帰を使うと簡単に定義できます。
List 8 : データの挿入
1 sub insert_tree {
2 my ($node, $item) = @_;
3 if( $node == $nil ){
4 my $new = {'item' => $item, 'left' => $nil, 'right' => $nil };
5 bless $new, 'Bintree';
6 return $new;
7 } else {
8 my $result = $item->compare( $node->{'item'} );
9 if( $result < 0 ){
10 $node->{'left'} = &insert_tree( $node->{'left'}, $item );
11 } elsif( $result > 0 ){
12 $node->{'right'} = &insert_tree( $node->{'right'}, $item );
13 }
14 }
15 $node;
16 }
3 行目で、節 $node が終端と等しいのであれば、新しい節を生成してデータ
$item をセットし、その節を返します。たとえば、$root が空の木であれば、新
しく生成された節が返されるので、$root に新しい木がセットされます。そうで
なければ、節に格納されているデータと比較します。$result が -1 であれば左
側の子をたどり、1 であれば右側の子をたどります。ここで再帰呼び出しが行わ
れます。ここでは呼び出す関数が決まっているので、メソッドの呼び出しではな
く関数形式で呼び出しています。そして、返された木を節にセットします。もし
も left や right にデータが無ければ、ここに新しい子が挿入されます。$item
と等しいデータが見つかった場合は、新しいデータを挿入する必要はないので、
何も行っていません。後は、データを挿入した部分木を返す、つまり、引数の
$node をそのまま返せばいいのです。結局、子を格納している節には、同じ子が
再度セットされることになります。無駄なように思われるかもしれませんが、そ
の分だけプログラムが簡単になるのです。
今回は再帰を使ってプログラミングしましたが、繰り返しに変換することもで
きます。興味のある方は挑戦してみてください。
○データの表示
最後にデータを表示するメソッド print_tree を作ります。ところで、木の全
ての節を規則的な順序で回ることを「巡回(traverse)」といいます。この中で重
要なのが次の方法です。
1. 行きがけ順
まず節のデータを出力し、その後、左の子、右の子の順番で出力。
2. 帰りがけ順
左の子、右の子を出力してから、節のデータを出力。
3. 通りがけ順
左の子を出力してから、節のデータを出力し、最後に右の子を出力。
名前の由来は、節のデータを出力するタイミングからきています。節に最初に到
達した時に出力するのが「行きがけ」、左右の子を出力して戻ってきた時に出力
するのが「帰りがけ」、左の子を出力して戻ってきた時に、右の子を出力する前
に節のデータを出力するのが「通りがけ」です。
二分探索木の場合、通りがけ順でデータを出力すると、ソートした出力結果を
得ることができます。それでは、print_tree を作りましょう。
List 9 : 二分探索木の表示
1 sub print_tree {
2 my $node = shift;
3 if( $node != $nil ){
4 &print_tree( $node->{'left'} );
5 $node->{'item'}->print_object();
6 &print_tree( $node->{'right'} );
7 }
8 }
print_tree も再帰を使えば簡単です。まず引数 $node が $nil でないことを確
認します。後は、左側の子をたどり、帰ってきたら節に格納されているインスタ
ンスを出力し、それから、右側の子をたどります。まさに、通りがけ順の定義そ
のものですね。インスタンスを表示するために print_object というメソッドを
呼び出しています。これはデータを比較するメソッド compare と同じく、クラ
スを作る時に定義しておきます。
この他に、二分探索木からデータを削除する操作もあるのですが、ちょっと難
しいので省略します。Ｃ言語でよければ、拙作の「Ｚしーモンキー第 12 回（月
刊・電脳倶楽部 Vol.95）」で詳しく説明しているので参考にしてください。
○実行例
それでは簡単な実行例を示しましょう。数値を格納するクラス Number を作っ
て動作の確認を行います。
List 10 : クラス Number の定義
1 package Number;
2
3 sub new {
4 my ($type, $num) = @_;
5 my $obj = { 'value' => $num };
6 bless $obj, 'Number';
7 $obj;
8 }
9
10 sub compare {
11 my ($obj1, $obj2) = @_;
12 $obj1->{'value'} <=> $obj2->{'value'};
13 }
14
15 sub print_object {
16 my $obj = shift;
17 print $obj->{'value'}, "\n";
18 }
インスタンスを生成するメソッド new は簡単ですね。これもインスタンスには
ハッシュを使っています。データを比較するメソッド compare と表示するメソ
ッド print_object を忘れずに定義します。それでは実際に使ってみます。
package main;
$root = Bintree->make_tree();
for( $i = 0; $i < 10; $i++ ){
my $num = rand();
my $obj = Number->new( $num );
$root = $root->insert_tree( $obj );
print $num, "\n";
}
print "---- output tree ----\n";
$root->print_tree();
乱数を 10 個生成して二分探索木に挿入します。実行結果は次のようになります。
0.86825561523438
0.8616943359375
0.65994262695313
0.69189453125
0.93524169921875
0.24749755859375
0.9453125
0.31430053710938
0.32781982421875
0.97140502929688
---- output tree ----
0.24749755859375
0.31430053710938
0.32781982421875
0.65994262695313
0.69189453125
0.8616943359375
0.86825561523438
0.93524169921875
0.9453125
0.97140502929688
正常に動作していますね。二分探索木を操作するクラスは一つですが、格納する
データをクラスで表し、データを比較するメソッド compare を定義することで、
あらゆるデータに対応することができます。
○次回は？
次回は、オブジェクト指向の目玉機能である「継承」を説明する予定です。お
楽しみに。
―参考文献―
[1] Larry Wall, Tom Christiansen, Randal L. Schwartz 共著「プログラミン
グＰｅｒｌ」改訂版 オライリー・ジャパン 1997
[2] Sriram Srinivasan 著「実用Ｐｅｒｌプログラミング」オライリー・ジャ
パン 1998
（ＥＯＦ）